{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #All Paths From Source to Target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: allPathsSourceTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有可能的路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个有&nbsp;<code>n</code>&nbsp;个节点的 <strong>有向无环图（DAG）</strong>，请你找出所有从节点 <code>0</code>&nbsp;到节点 <code>n-1</code>&nbsp;的路径并输出（<strong>不要求按特定顺序</strong>）</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />&nbsp;<code>graph[i]</code>&nbsp;是一个从节点 <code>i</code> 可以访问的所有节点的列表（即从节点 <code>i</code> 到节点&nbsp;<code>graph[i][j]</code>存在一条有向边）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/28/all_1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,2],[3],[3],[]]\n",
    "<strong>输出：</strong>[[0,1,3],[0,2,3]]\n",
    "<strong>解释：</strong>有两条路径 0 -&gt; 1 -&gt; 3 和 0 -&gt; 2 -&gt; 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/28/all_2.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[4,3,1],[3,2,4],[3],[4],[]]\n",
    "<strong>输出：</strong>[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == graph.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 15</code></li>\n",
    "\t<li><code>0 &lt;= graph[i][j] &lt; n</code></li>\n",
    "\t<li><code>graph[i][j] != i</code>（即不存在自环）</li>\n",
    "\t<li><code>graph[i]</code> 中的所有元素 <strong>互不相同</strong></li>\n",
    "\t<li>保证输入为 <strong>有向无环图（DAG）</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [all-paths-from-source-to-target](https://leetcode.cn/problems/all-paths-from-source-to-target/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [all-paths-from-source-to-target](https://leetcode.cn/problems/all-paths-from-source-to-target/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[3],[3],[]]', '[[4,3,1],[3,2,4],[3],[4],[]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        result = []\n",
    "\n",
    "        def backtrack(currnode, path):\n",
    "            if currnode == len(graph) - 1:\n",
    "                result.append(list(path))\n",
    "                return\n",
    "\n",
    "            for element in graph[currnode]:\n",
    "                path.append(element)\n",
    "                backtrack(element, path)\n",
    "                path.pop()\n",
    "\n",
    "        path = [0]\n",
    "        backtrack(0, path)\n",
    "\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __dfs(self, index):\n",
    "        self.__rec.append(index)\n",
    "        if index == len(self.__graph) - 1:\n",
    "            self.__ans.append(self.__rec[:])\n",
    "        else:\n",
    "            for i in self.__graph[index]:\n",
    "                self.__dfs(i)\n",
    "        self.__rec.pop()\n",
    "\n",
    "    def allPathsSourceTarget(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.__graph, self.__ans, self.__rec = graph, [], []\n",
    "        self.__dfs(0)\n",
    "        return self.__ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        now = [0]\n",
    "        res = self.dfs(graph,0,now,[])\n",
    "        return res\n",
    "\n",
    "    def dfs(self,graph,n,now,res):\n",
    "        if len(graph[n]) == 0:\n",
    "            res.append(now[:])\n",
    "            return\n",
    "        else:\n",
    "            for i in range(len(graph[n])):\n",
    "                now.append(graph[n][i])\n",
    "                self.dfs(graph,graph[n][i],now,res)\n",
    "                now.pop()\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def dfs(node, pre = [0]):\n",
    "            for i in graph[node]:\n",
    "                if i == n - 1:\n",
    "                    ans.append(pre + [i])\n",
    "                else:\n",
    "                    dfs(i, pre + [i])\n",
    "        \n",
    "        ans, n = [], len(graph)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        steps=[0]\n",
    "        def findGraph():\n",
    "            nonlocal res,steps\n",
    "            if graph[steps[-1]]==[]:\n",
    "                res.append(steps[:])\n",
    "                return\n",
    "            for i in range(len(graph[steps[-1]])):\n",
    "                steps.append(graph[steps[-1]][i])\n",
    "                findGraph()\n",
    "                print(steps)\n",
    "                steps.pop()\n",
    "        findGraph()\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.ans=[]\n",
    "        n=len(graph)-1\n",
    "        def DFS(point,path):\n",
    "            if point==n:\n",
    "                self.ans.append(path)\n",
    "                return None\n",
    "            else:\n",
    "                for item in graph[point]:\n",
    "                    DFS(item,path+[item])\n",
    "        DFS(0,[0])\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        num_node = []\n",
    "        for lines in graph:\n",
    "            if not lines:\n",
    "                graph.remove(lines)\n",
    "                continue\n",
    "            num_node.append(max(lines))\n",
    "        max_node = max(num_node)\n",
    "        result = []\n",
    "        temps = [[max_node]]\n",
    "        for temp in temps:\n",
    "            for i in range(len(graph)):\n",
    "                if temp[0] in graph[i]:\n",
    "                    sub_temp = [i]\n",
    "                    sub_temp.extend(temp)\n",
    "                    temps.append(sub_temp)\n",
    "        for temp in temps:\n",
    "            if temp[0] == 0:\n",
    "                result.append(temp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        row = len(graph)\n",
    "        res=[]\n",
    "        def dfs(start, path):\n",
    "            if start == row-1:\n",
    "                res.append(path)\n",
    "            for node in graph[start]:\n",
    "                dfs(node,path + [node])\n",
    "        dfs(0, [0])\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def allPathsSourceTarget(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        begin = [[0]]\n",
    "        def findNext(self,source,graph):\n",
    "            if source == []:\n",
    "                return\n",
    "            final = []\n",
    "            for i in source:\n",
    "                if graph[i[-1]] == []:\n",
    "                    pass\n",
    "                else:\n",
    "                    for x in graph[i[-1]]:\n",
    "                        temp = copy.deepcopy(i)\n",
    "                        if x == len(graph) - 1:\n",
    "                            temp.append(x)\n",
    "                            self.res.append(temp)\n",
    "                        else:\n",
    "                            temp.append(x)\n",
    "                            final.append(temp)\n",
    "            findNext(self,final,graph)\n",
    "        findNext(self,begin,graph)\n",
    "        return self.res\n",
    "                    \n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        rnc = []\n",
    "        dq = collections.deque()\n",
    "        dq.append([0])\n",
    "        n = len(graph)-1\n",
    "        while dq:\n",
    "            cur = dq.pop()\n",
    "            num = cur[-1]\n",
    "            if num == n:\n",
    "                rnc.append(cur)\n",
    "                continue\n",
    "            for nnum in graph[num]:\n",
    "                dq.append(cur.copy()+[nnum])\n",
    "        return rnc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        path = [0]\n",
    "        return self.helper(graph,graph[0],path,[])\n",
    "\n",
    "    \n",
    "    def helper(self,origraph,nodes,path,ans):\n",
    "        if path[-1] == len(origraph) - 1:\n",
    "            ans.append(path)\n",
    "\n",
    "        for node in nodes:\n",
    "            Path = path + [node]\n",
    "            Nodes = origraph[node]\n",
    "            self.helper(origraph,Nodes,Path,ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        def helper(path, visited):\n",
    "            # print(path, visited, self.paths)\n",
    "            if path[-1] == len(graph)-1:\n",
    "                self.paths.append(path[:])\n",
    "                return\n",
    "            for i in graph[path[-1]]:\n",
    "                if i not in visited:\n",
    "                    path.append(i)\n",
    "                    visited.add(i)\n",
    "                    helper(path, visited)\n",
    "                    visited.remove(i)\n",
    "                    path.pop(-1)\n",
    "        self.paths = []\n",
    "        helper([0], {0})\n",
    "        return self.paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        k=len(graph)-1\n",
    "        def back(tmp,cur):\n",
    "            if cur==k:\n",
    "                res.append(tmp)\n",
    "                return\n",
    "            for i in graph[cur]:\n",
    "                back(tmp+[i],i)\n",
    "        back([0],0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        \n",
    "        def dfs(indx,tmp):\n",
    "            if indx!=len(graph)-1:\n",
    "                if graph[indx]:\n",
    "                    for i in graph[indx]:\n",
    "                        dfs(i,tmp+[i])\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "        dfs(0,[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        N = len(graph)\n",
    "\n",
    "        def solve(node):\n",
    "            if node == N-1: return [[N-1]]\n",
    "            ans = []\n",
    "            for nei in graph[node]:\n",
    "                for path in solve(nei):\n",
    "                    ans.append([node] + path)\n",
    "            return ans\n",
    "\n",
    "        return solve(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def allPathsSourceTarget(self, graph):\n",
    "        N = len(graph)\n",
    "\n",
    "        def solve(node):\n",
    "            if node == N-1: return [[N-1]]\n",
    "            ans = []\n",
    "            for nei in graph[node]:\n",
    "                for path in solve(nei):\n",
    "                    ans.append([node] + path)\n",
    "            return ans\n",
    "\n",
    "        return solve(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        path = []\n",
    "        self.traverse(graph,0,path)\n",
    "        return self.res\n",
    "    \n",
    "    def traverse(self,graph,s,path):\n",
    "        # s是当前节点值，起点\n",
    "        # path 记录路径\n",
    "        path.append(s)\n",
    "        if s == len(graph)-1:\n",
    "            self.res.append(tuple(path))\n",
    "            path.pop()\n",
    "            return\n",
    "        \n",
    "\n",
    "        for nb in graph[s]:\n",
    "            # 遍历当前节点的邻接节点\n",
    "            self.traverse(graph,nb,path)\n",
    "        path.pop()\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.res = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        s = [(0,)]\n",
    "        while s:\n",
    "            curr_path = s.pop()\n",
    "            curr_node = curr_path[-1]\n",
    "            \n",
    "            if curr_node == len(graph) - 1:\n",
    "                res.append(curr_path)\n",
    "                continue\n",
    "\n",
    "            for next_node in graph[curr_node]:\n",
    "                s.append(curr_path + (next_node, ))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        self.graph = graph\n",
    "        self.seqs = []\n",
    "        self.nodes_num = len(graph)\n",
    "        self.dfs([0])\n",
    "        return self.seqs\n",
    "\n",
    "    def dfs(self, cur_seq):\n",
    "        cur_node = cur_seq[-1] \n",
    "        if cur_node == self.nodes_num - 1:\n",
    "            self.seqs.append((*cur_seq,))\n",
    "            return\n",
    "        \n",
    "        for node in self.graph[cur_node]:\n",
    "            cur_seq.append(node)\n",
    "            self.dfs(cur_seq)\n",
    "            cur_seq.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph):\n",
    "        if len(graph) == 0 and len(graph[0]) == 0:\n",
    "            return []\n",
    "        \n",
    "        self.ans = []\n",
    "        self.record = [0]\n",
    "        self.dfs(graph, 0)\n",
    "\n",
    "        return self.ans\n",
    "    \n",
    "    def dfs(self, graph, x):\n",
    "        if x == len(graph) - 1:\n",
    "            self.ans.append(self.record[:])\n",
    "            return\n",
    "        \n",
    "        for i in graph[x]:\n",
    "            self.record.append(i)\n",
    "            self.dfs(graph, i)\n",
    "            self.record.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        end = len(graph) - 1\n",
    "        q = [[0, [0]]]\n",
    "        while len(q) != 0:\n",
    "            node, path = q.pop(0)\n",
    "            for move in graph[node]:\n",
    "                cp = deepcopy(path)\n",
    "                cp.append(move)\n",
    "                if move != end:\n",
    "                    q.append([move, cp])\n",
    "                else:\n",
    "                    ans.append(deepcopy(cp))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = list()\n",
    "        stk = list()\n",
    "        n = len(graph)\n",
    "        def dfs(i):\n",
    "            if i == n - 1:\n",
    "                ans.append(stk[:])\n",
    "                return \n",
    "            for j in graph[i]:\n",
    "                stk.append(j)\n",
    "                dfs(j)\n",
    "                stk.pop()\n",
    "        stk.append(0)\n",
    "        dfs(0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        queue = []\n",
    "        n = len(graph)\n",
    "        ans = []\n",
    "        queue.append([0])\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            for i in range(l):\n",
    "                cur = queue.pop(0)\n",
    "                for j in graph[cur[-1]]:\n",
    "                    t = cur.copy()\n",
    "                    t.append(j)\n",
    "                    if j == n - 1:\n",
    "                        ans.append(t)\n",
    "                        continue\n",
    "                    queue.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(node, path, res):\n",
    "            if path[-1] == len(graph) - 1:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i in range(len(node)):\n",
    "                dfs(graph[node[i]], path+[node[i]], res)\n",
    "            return res\n",
    "        return dfs(graph[0], [0], [])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.path = [0] # 从节点0开始\n",
    "\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        if not graph:\n",
    "            return []\n",
    "\n",
    "        self.dfs(graph, 0)\n",
    "\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self, graph, root):\n",
    "        if root == len(graph)-1:\n",
    "            self.res.append(self.path[:])\n",
    "            return\n",
    "        \n",
    "        for node in graph[root]:\n",
    "            self.path.append(node)\n",
    "            self.dfs(graph, node)\n",
    "            self.path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.path = [0] # 从节点0开始\n",
    "\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        if not graph:\n",
    "            return []\n",
    "        self.dfs(graph, 0)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self, graph, root):\n",
    "        if root == len(graph)-1:\n",
    "            self.res.append(self.path[:])\n",
    "            return\n",
    "        \n",
    "        for node in graph[root]:\n",
    "            self.path.append(node)\n",
    "            self.dfs(graph, node)\n",
    "            self.path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        end = len(graph)\n",
    "        used = [False]*end\n",
    "        path= [0]\n",
    "        result = []\n",
    "        def dfs(node):\n",
    "            if end-1 == node:\n",
    "                result.append(path[::])\n",
    "            for link_node in graph[node]:\n",
    "                if not used[link_node]:\n",
    "                    # print(link_node)\n",
    "                    path.append(link_node)\n",
    "                    used[link_node]=True\n",
    "                    dfs(link_node)\n",
    "                    used[link_node]=False\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return result\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        # 从答案的角度\n",
    "        n = len(graph)\n",
    "        def dfs(i):\n",
    "            path.append(i)\n",
    "            if i == n-1:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "                \n",
    "            for j in graph[i]:\n",
    "                dfs(j)\n",
    "                path.pop()\n",
    "        \n",
    "        res, path = [], []\n",
    "        dfs(0)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
